#include <iostream>
#include <vector>
#include <math.h>

using namespace std;

vector<int> p;

bool prime(int k)
{
	for (int i = 0; i < (int) p.size(); i++) 
	{
		if (p[i] > sqrt(k)) break;

		if (k % p[i] == 0) return false;
	}
	return true;
}

void genp()
{
	for (int i = 2; i < 32000; i++) 
		if (prime(i)) p.push_back(i);
}

int sumDig(long long k)
{
	int sum = 0;
	while (k > 0)
	{
		sum += k%10;
		k /= 10;
	}
	return sum;
}

bool isSmith(long long n)
{
	if (prime(n)) return false;

	int m = n, sum = 0;
	for (int i = 0; i < (int) p.size(); i++) 
	{
		if (p[i] > sqrt(n)) break;
		int dig = sumDig(p[i]);
		while (n % p[i] == 0)
		{
			n = n/p[i];
			sum += dig;
		}
	}
	if (n > 1) sum += sumDig(n);

	if (sum == sumDig(m)) return true;
	return false;
}

long long cal(long long n)
{
	while (!isSmith(n+1)) n++;
	return n+1;
}


int main()
{
	genp();
	int ntest;
	cin >> ntest;
	while (0 < ntest--)
	{
		long long n;
		cin >> n;
		cout << cal(n) << endl;
	}
	return 0;
}
